#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;
const int N=1e5+10;
int n,m;
struct edge
{
    int to;
    int next;
    int id;//边号
}edges[N];
bool st[N];
int cnt=1;
vector<int> pathnode;
vector<int> pathside;
int head[N];
vector<pp> ques;
vector<int> sidecount(N,0);
void add(int u,int v,int id)
{
    edges[cnt].id=id;
    edges[cnt].to=v;
    edges[cnt].next=head[u];
    head[u]=cnt++;
}
bool dfs(int s,int end)
{
    st[s]=true;
    pathnode.push_back(s);
    if(s==end) return true;
    for(int i=head[s];i!=1;i=edges[i].next)
    {
        int j=edges[i].to;
        int cid=edges[i].id;
        if(!st[j])
        {
            if(dfs(j,end))
            {
                pathside.push_back(cid);
                return true;
            }
            st[j]=false;
            pathnode.pop_back();
            pathside.pop_back();
        }
    }
    return false;
}
void init()
{
    memset(st,0,sizeof(st));
    pathnode.clear();
    pathside.clear();
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v,1);
        add(v,u,1);
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        ques.push_back(make_pair(a,b));
    }
    init();
    dfs(3,6);
    for(auto&ch:pathnode) cout<<ch<<" ";
    cout<<endl;


    for(auto&ch:pathside) cout<<ch<<" ";
    cout<<endl;
}